Computers utilize a wide variety of disks to store data. Disks are classified according to the storage medium employed, such as when "optical" disks are distinguished from "magnetic" disks. Disks are also classified as either "floppy" or "hard." Hard disks generally have greater storage capacity, faster data access times, and longer useful lives than floppy disks ("floppies"). Unlike hard disks, however, floppies are "removable." That is, floppies are easily released from, and reattached to, a disk drive which provides the computer with access to the data on the disk.
FIG. 1 illustrates a disk 2 attached to a disk drive 4. The disk drive 4 is in signal communication with a computer system 6 which makes read and write requests of the disk drive 4. The computer system 6 comprises at least one processor ("CPU") 8 which is in digital signal communication with a memory 10. Suitable memories 10 include random access memory, read-only memory, and combinations of these two memory types.
The computer system 6 is also capable of comprising at least one program storage medium 12. Suitable storage media 12 include a magnetic, optical, or other computer-readable storage device having a specific physical substrate configuration. Suitable storage devices include floppy disks, hard disks, tape, CD-ROMs, PROMs, RAM, and other computer system storage devices.
The substrate configuration represents data and instructions which cause the computer system to operate in a specific and predefined manner as described herein. Thus, the medium 12 tangibly embodies a program, functions, and/or instructions that are executable by the processor 8 to perform disk partition manipulation steps according to the present invention. In some embodiments according to the present invention, the instructions are stored on a medium 12 that also contains the disk partition being manipulated. In other embodiments, the instructions are stored on one instance of a medium 12 and the disk partition of one or more other media 12 are manipulated.
The disk 2 illustrates physical characteristics of both floppies and hard disks. The disk 2 contains a number of concentric data cylinders such as the cylinder 14. The cylinder 14 contains several data sectors, including sectors 16 and 18. The sectors 16 and 18 are located on an upper side 20 of the disk 2; additional sectors may be located on a lower side 22 of the disk 2. The sides 20, 22 of the disk 2 define a platter 24. Floppy disks contain only one platter and thus are either single-sided or double-sided. For clarity of illustration only one platter 24 is shown in FIG. 1, but hard disks often contain several platters and thus may include one, two, or more sides.
The upper side 20 of the disk 2 is accessed by a head 26 mounted on an arm 28 secured to the drive 4. To access different cylinders of the disk 2, the arm 28 moves the head 26 in toward the center of the disk 2 or out toward the periphery of the disk 2 according to the position of the desired cylinder. To access different sectors within a cylinder, the drive 4 rotates the disk 2 around a spindle 30, thereby rotating the desired sectors into adjacency with the head 26. Additional sides of a disk,including sides on additional platters, may be accessed in a similar manner by additional disk drive heads. Because each side of a disk is accessed by a corresponding disk drive head, the number of heads is sometimes used to indicate the number of sides of the disk that are accessible to the drive. For example, double-sided disks are accessed with double-headed drives.
A given sector on the disk 2 may be identified by specifying a head, a cylinder, and a sector within the cylinder. Heads are generally numbered from the top of the drive proceeding downward, beginning at zero. Cylinders are generally numbered from the outside edge of the platter proceeding inward, beginning at zero. Sectors within a cylinder are generally numbered from a marker in the disk medium proceeding either clockwise or counterclockwise, depending on the direction of disk rotation in the disk drive, and beginning at one. A triplet specifying the head number, cylinder number, and sector number in this manner is known as a "physical sector address." For instance, the sector labeled as 16 in FIG. 1 could have a physical sector address of (head zero, cylinder seven, sector two), or more concisely, a physical address of (0, 7, 2). The terms "address" and "pointer" are used interchangeably herein.
Alternatively, a given sector may be identified by a "logical sector address." Each logical sector address is a single number rather than a triplet of numbers. The logical address of a sector corresponds to the number of sectors between the addressed sector and the "first" sector on the disk 2 along some specified path which traverses all available sectors in order. The first sector, known as "sector zero," is often located at a physical sector address of (0, 0, 1). One common traversal path begins at logical sector zero, traverses the sectors in cylinder zero of head zero, traverses the sectors of cylinder zero of head one, proceeds thus through cylinder zero on each successive head, proceeds to the sectors of cylinder one of head zero, and continues in like manner. However, other disk traversal paths are also used.
The sector (exemplified by sectors 16, 18) is the smallest unit of individually addressable disk storage recognized by the disk drive 4. An individual bit within any sector can be altered only by reading the entire sector into a memory buffer, overwriting the bit in question, and then writing the entire sector back onto the disk 2.
However, software executing on the processor 8 does not always operate on individual sectors. In particular, "file system" software which helps define the format used to organize data on the disk 2 and file system "drivers" which actuate the disk drive 4 to read and write that data do not necessarily treat sectors as the smallest addressable storage unit. One commonly used file system, the File Allocation Table ("FAT") file system, is configured to allocate sectors in "clusters" of one or more sectors each. Each cluster contains 2.sup.n sectors, where n is in the range from zero to Max and Max gives a cluster size of 64K bytes. The value of n is fixed when the disk 2 is initially formatted, and does not typically change during use of the disk 2. The cluster size can be changed with conventional tools by reformatting the disk 2, but such reformatting is destructive, as it destroys access to all user data that was stored in the reformatted region.
File systems are generally used in combination with "partitions" to define the physical organization of data on the disk. Partitions are often defined by the contents of a "partition table" which is located on the disk 2. For instance, MACINTOSH.RTM. computers utilize a partition table having a composition that is specifically adapted for use with the MACINTOSH operating system (MACINTOSH is a registered trademark of Apple Computer, Inc.). Many SUN.RTM. workstation computers utilize a partition table composition that is specifically adapted for use with the SunOS.RTM. File System (SUN and SunOS are registered trademark of Sun Microsystems, Inc.). Other examples abound; different partition table compositions are almost as common as different operating systems and different file systems, which number in the hundreds.
Unfortunately, different partition table compositions are usually incompatible. Detailed methods which correctly modify the contents of a first partition table will often scramble the contents of a second partition table if the first and second tables use different composition rules. A detailed method for reducing the number of disk sectors in a MACINTOSH partition, for instance, is likely to be of little help in shrinking a SunOS partition, and may even cause data loss if applied to the SunOS partition table.
One partition table composition, denoted herein as the "IBM-compatible" partition table, is found on the disks used in many IBM.RTM. personal computers and IBM-compatible computers (IBM is a registered trademark of International Business Machines Corporation). IBM-compatible partition tables may be used on both floppies and hard disks, and they may be used with magnetic disks, optical disks, and disks employing other storage media. IBM-compatible partition tables may also be used with a variety of disk sector addressing schemes, including without limitation schemes that employ traversal paths different from the path described above and schemes which assign logical sector addresses that start over again at zero for each partition on the disk.
As shown in FIG. 2, an IBM-compatible partition table 32 includes an Initial Program Loader ("IPL") identifier 34, four primary partition identifiers 36, and a boot identifier 38. As shown in FIG. 3, each partition identifier 36 includes a boot indicator 40 to indicate whether the partition in question is bootable. At most one of the partitions in the set of partitions defined by the partition table 32 is bootable at any given time.
Each partition identifier 36 also includes a starting address 42, which is the physical sector address of the first sector in the partition in question, and an ending address 44, which is the physical sector address of the last sector in the partition. A sector count 46 holds the total number of disk sectors in the partition. A boot sector address 48 holds the logical sector address corresponding to the physical starting address 42. On disks having more than 1024 cylinders, the starting address 42 and the ending address 44 contain predetermined maximum values if the actual values are too large to store in the space given in the partition table 32; the actual values can be derived from the sector count 46 and the boot sector address 48.
Some IBM-compatible computer systems allow "logical partitions" as well as the primary partitions just described. All logical partitions are contained within one primary partition; a primary partition which contains logical partitions is also known as an "extended partition." Logical partitions are represented by one or more lists of partition identifiers 36. Each list is attached in conventional fashion to one of the partition identifiers P1, P2, P3, or P4. Thus, the set of partitions defined by an IBM-compatible partition table includes any defined primary partition, regardless of whether that primary partition is an extended partition, and also includes any logical partitions defined by partition identifiers 36.
Each partition identifier 36 also includes a system indicator 50. The system indicator 50 identifies the type of file system contained in the partition, which in turn-defines the physical arrangement of data that is stored in the partition on the disk 2 (FIG. 1). The system indicator 50 utilizes predefined constant values to designate various file systems. For instance, the constant value 01H indicates a 12-bit FAT file system of the type first used by the MS-DOS.RTM. operating system (MS-DOS is a registered trademark of Microsoft Corporation). Other values designate other file systems, including the CP/M-86.RTM. file system (registered trademark of Novell, Inc), the XENIX.RTM. file system (registered trademark of Microsoft Corporation), the NOVELL file system (trademark of Novell, Inc.), a 16-bit FAT file system of the MS-DOS operating system, and the PCIX file system. Values not recognized by a particular operating system are treated as designating an unknown file system.
The system indicator 50 may designate a file system, such as the 12-bit FAT file system, which is used most widely in connection with a particular operating system, such as MS-DOS. However, operating systems and file systems are different components of the computer. The file system associated with a specific partition of the disk 2 (FIG. 1) determines the format in which data is stored in the partition, namely, the physical arrangement of user data and of file system structures in the portion of the disk 2 that is delimited by the starting address 42 and the ending address 44 of the partition in question. At any given time, each partition thus contains at most one type of file system.
The operating system manages access, not only to the disk 2, but to other computer resources as well. Resources typically managed by the operating system include one or more disks and disk drives, memory (RAM and/or ROM), microprocessors, and I/O devices such as a keyboard, mouse, screen, printer, tape drive, modem, serial port, parallel port, or network port.
The operating system accesses the disk 2 in part-through file system drivers. These drivers use internal file system data and assumptions about the file system to translate more abstract information such as file names and read/write requests into more detailed information such as sector addresses and physical disk accesses. By appropriate use of file system drivers, a single operating system can access files stored according to different file systems. For instance, the OS/2 operating system can access both FAT files and High Performance File System ("HPFS") files (OS/2 is a mark of International Business Machines Corporation). File system drivers do not alter the type of file system that is contained in a partition. Nor do file system drivers alter characteristics such as the partition's size, the partition's location on the disk 2 (FIG. 1), or the cluster size of FAT partitions.
It is sometimes desirable to alter the contents of an IBM-compatible partition table. For instance, a person using a computer may wish to expand a particular partition to allow additional data to be stored in files within that partition. Conversely, the user may wish to shrink a specified partition by allocating fewer disk sectors to the partition. It may also be convenient or necessary to move a partition to a different location on the disk while substantially or exactly preserving the number of disk sectors allocated to the partition.
One conventional approach to modification of an IBM-compatible partition table begins by copying all necessary user and system data off the disk to a temporary storage location such as a tape or another disk. The data copied includes without limitation the contents of files created by the user such as textual documents and spreadsheets, the contents of files required to run applications such as word processors, and system data such as directory information. Some internal file system data such as sector allocation maps does not necessarily need to be copied, but is often copied anyway. The familiar disk utility FDISK is then used to update the IBM-compatible partition table. The newly specified partition is then formatted with the familiar disk utility FORMAT or a similar utility. Finally, the data is copied back into the new partition on the disk. During this copying process the file system copy utility creates appropriate new file system structures reflecting the current locations of data on the disk.
This approach to partition manipulation has several drawbacks. A temporary storage device with adequate storage capacity may not be readily available or affordable under the circumstances. Even if temporary storage is available, copying large amounts of data from the disk to temporary storage and then back again can take a substantial period of time.
In addition, manipulating IBM-compatible partition tables in this manner is confusing and dangerous for many computer users. The FDISK utility assumes that the user is familiar with the intricacies of IBM-compatible partition tables, physical disk addresses, logical partitions, extended partitions; operating system assumptions regarding partitions, cluster sizes, file allocation tables, and related matters. Users who are unfamiliar with these technical details may easily and inadvertently destroy data.
Less grievous but nonetheless undesirable situations can also arise if the user miscalculates the correct size or position of the new partitions. For instance, if the partition has been made too small to receive all the data from temporary storage, it becomes necessary to once again modify the partition table with FDISK, to reformat again, and to once again copy all the data from temporary storage into the reformatted partition. Even if everything works as desired the first time, this approach to partition modification can be very time-consuming. With a typical disk holding several hundred megabytes of data the process may require several hours to complete successfully.
Some conventional partition manipulation approaches are limited to shrinking partitions. They provide no capability for expanding a partition or moving a partition to a new location on the disk while preserving the partition's size. Moreover, known approaches allow user data to be lost if power to the computer is interrupted during the partition shrinking operation.
In addition, the only previously known approach to resizing clusters in FAT partitions is destructive reformatting of the disk partition.
Moreover, known approaches to partition resizing are not integrated with means for checking the integrity and self-consistency of the file system before and after the operation. One partition resizing approach requires a shift in position of all clusters, thereby significantly increasing not only the time required to resize but also the risk of data corruption if resizing is interrupted. Moreover, such approaches lose data if any bad sectors are present in the disk partition. Finally, some known partition resizing operations do not properly handle conditions that often arise in the file system structures as a result of resizing.
Thus, it would be an advancement in the art to provide a method that allows users who are unfamiliar with technical intricacies to easily resize and reconfigure IBM-compatible disk partitions without destroying any user data.
It would also be an advancement to provide such a method which either increases or decreases FAT cluster size, as desired.
It would be a further advancement to provide such a method which prevents data loss caused by interruptions such as a power failure during the manipulation of a partition.
It would also be an advancement to provide such a method which properly resizes and reconfigures logical partitions and extended partitions.
It would be a further advancement to provide such a method which efficiently tests the integrity and consistency of the file system data within a partition.
Such a method for manipulating disk partitions is disclosed and claimed herein.